package com.kehao.leetcode.hard.linkedlist;


import org.junit.Test;

import java.util.List;
import java.util.PriorityQueue;

public class MergeKListsSolution {
    private class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    private ListNode makeLinkedList(int[] nums){
        ListNode head = new ListNode();
        ListNode p = head;
        for (int i = 0; i < nums.length; i++) {
            p.next = new ListNode(nums[i]);
            p = p.next;
        }
        return head.next;
    }
    private ListNode[] makeLists( int[][] lists){
        ListNode[] array = new ListNode[lists.length];
        for (int i = 0; i < lists.length; i++) {
            array[i] = makeLinkedList(lists[i]);
        }
        return array;
    }

    private void printLinkedList(ListNode node){
        while (node!=null){
            System.out.print(node.val);
            node=node.next;
        }
        System.out.println();
    }

    //直接合并
    public ListNode mergeKLists01(ListNode[] lists) {
        ListNode head = new ListNode();
        ListNode p = head;
        ListNode[] pl = new ListNode[lists.length];
        int nullCount = 0;
        for (int i = 0; i < pl.length; i++) {
            pl[i]=lists[i];
            if(pl[i]==null)nullCount++;
        }

        while (nullCount<lists.length){
            int min = Integer.MAX_VALUE;
            int pos = 0;
            for (int i = 0; i < pl.length; i++) {
                if(pl[i]!=null){
                    if(min>pl[i].val){
                        min = pl[i].val;
                        pos = i;
                    }
                }
            }
            p.next = pl[pos];
            pl[pos] = pl[pos].next;
            p = p.next;
            if(pl[pos]==null) nullCount++;
        }

        return head.next;
    }

    //通过两个合并的方法进行递归
    public ListNode mergeKLists02(ListNode[] lists) {
        ListNode listNode = mergeKLists(lists,0, lists.length);
        return listNode;
    }
    private ListNode mergeKLists(ListNode[] lists,int start,int end){
        if(end==start){
            return null;
        }
        if(end==start+1){
            return lists[start];
        }
        if(end==start+2){
            return merge2Lists(lists[start],lists[start+1]);
        }
        int mid = (start+end+1)/2;
        return merge2Lists(mergeKLists(lists,start,mid),mergeKLists(lists,mid,end));
    }
    private ListNode merge2Lists(ListNode listNode1,ListNode listNode2){
        ListNode head = new ListNode();
        ListNode p = head;
        if(listNode1 == null) return listNode2;
        if(listNode2 == null) return listNode1;
        while (listNode1!=null&&listNode2!=null){
            if(listNode1.val <  listNode2.val){
                p.next = listNode1;
                listNode1 = listNode1.next;
            }else {
                p.next = listNode2;
                listNode2 = listNode2.next;
            }
            p = p.next;
        }
        if(listNode1!=null){
            p.next = listNode1;
        }else if(listNode2!=null){
            p.next = listNode2;
        }
        return head.next;
    }

    //使用优先队列的方法
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        ListNode head = new ListNode();
        ListNode p = head;
        for (int i = 0; i < lists.length; i++) {
            while (lists[i]!=null){
                priorityQueue.add(lists[i].val);
                lists[i] = lists[i].next;
            }
        }
        while (!priorityQueue.isEmpty()){
            p.next = new ListNode(priorityQueue.poll());
            p = p.next;
        }
        return head.next;
    }

    //lists = [[1,4,5],[1,3,4],[2,6]]
    @Test
    public void test01(){
        int[][] listsArray = {{1,4,5},{1,3,4},{2,6}};
        ListNode[] lists = makeLists(listsArray);
        for (int i = 0; i < lists.length; i++) {
            printLinkedList(lists[i]);
        }
        ListNode listNode = mergeKLists(lists);
        printLinkedList(listNode);
    }

    @Test
    public void test02(){
        int[][] listsArray = {};
        ListNode[] lists = makeLists(listsArray);
        for (int i = 0; i < lists.length; i++) {
            printLinkedList(lists[i]);
        }
        ListNode listNode = mergeKLists(lists);
        printLinkedList(listNode);
    }

    @Test
    public void test03(){
        int[][] listsArray = {{}};
        ListNode[] lists = makeLists(listsArray);
        for (int i = 0; i < lists.length; i++) {
            printLinkedList(lists[i]);
        }
        ListNode listNode = mergeKLists(lists);
        printLinkedList(listNode);
    }


}
